#ifndef __QUICKSORTER_H
#define __QUICKSORTER_H

#include <stdlib.h>
#include <string.h>

/** Quick sorting template class. */
template <class T>
class Quicksorter
{
   public:
      static void quicksortNArray(void **items, int noofsortarrays, T *metric, int total, size_t itemsize);
      static void quicksort(void *items, T *metric, int total, size_t itemsize);
   private:
      static void recurseQuicksortNArray(void **items, int noofsortarrays, T *metric, size_t itemsize, int left, int right);
      static int recursePartitioningNArray(void **items, int noofsortarrays, T *metric, size_t itemsize, int left, int right, int pivot);
      static void recurseQuicksort(void *items, T *metric, size_t itemsize, int left, int right);
      static int recursePartitioning(void *items, T *metric, size_t itemsize, int left, int right, int pivot);
      static void recurseSwap(void *items, size_t itemsize, int a, int b, void *tmp);
};

/** Quick sort an array of items. The array of items is accompanied by
 * a metric array; an array of numbers which are the result of some
 * objective function. Both are sorted according to the given metric.
 * 
 * @param items The items to sort as a void pointer pointing to a
 * contiguous array of items.
 * 
 * @param metric The metric array of type T in the template is used to
 * sort the lists.
 * 
 * @param total The number of entries in the items and metric lists to
 * sort.
 * 
 * @param itemsize The size of each of the items to sort. */
template <class T> void Quicksorter<T>::quicksort(void *items, T *metric, int total, size_t itemsize)
{
   // Wrapper for recursive quicksort that makes implementation
   // independant sense
   recurseQuicksort(items, metric, itemsize, 0, total - 1);
}

/** Quick sort n arrays of items. The array of items is accompanied by
 * a metric array; an array of numbers which are the result of some
 * objective function. Both are sorted according to the given metric.
 * 
 * @param items An array of arrays of items to sort as a void pointer
 * pointer pointing to a contiguous array of item array pointers.
 * 
 * @param noofsortarrays The number of arrays to sort included in the
 * array of items arrays.
 * 
 * @param metric The metric array of type T in the template is used to
 * sort the lists.
 * 
 * @param total The number of entries in the items and metric lists to
 * sort.
 * 
 * @param itemsize The size of each of the items to sort. */
template <class T> void Quicksorter<T>::quicksortNArray(void **items, int noofsortarrays, T *metric, int total, size_t itemsize)
{
   // Wrapper for recursive quicksort that makes implementation
   // independant sense
   recurseQuicksortNArray(items, noofsortarrays, metric, itemsize, 0, total - 1);
}

/** Quick sort an array of items. The array of items is accompanied by
 * a metric array; an array of numbers which are the result of some
 * objective function. Both are sorted according to the given metric.
 * 
 * @param items The items to sort as a void pointer pointing to a
 * contiguous array of items.
 * 
 * @param metric The metric array of type T in the template is used to
 * sort the lists.
 * 
 * @param itemsize The size of each of the items to sort.
 * 
 * @param left The left most item to include in the sort.
 * 
 * @param right The right most item to include in the sort. */
template <class T> void Quicksorter<T>::recurseQuicksort(void *items, T *metric, size_t itemsize, int left, int right)
{
   // if the left element number is smaller than the right element
   // number (sanity check)
   if (left < right)
   {
      // randomise pivot as one somewhere between the left element and
      // right element
      int firstpivot = (rand() % ((right + 1) - left)) + left;
      // do partitioning into list a (below pivot) and list b (above
      // pivot)
      int pivotnewindex = recursePartitioning(items, metric, itemsize, left, right, firstpivot);
      // quicksort list a
      recurseQuicksort(items, metric, itemsize, left, pivotnewindex - 1);
      // quicksort list b
      recurseQuicksort(items, metric, itemsize, pivotnewindex + 1, right);
   }
}

/** Quick sort n arrays of items. The array of items is accompanied by
 * a metric array; an array of numbers which are the result of some
 * objective function. Both are sorted according to the given metric.
 * 
 * @param items An array of arrays of items to sort as a void pointer
 * pointer pointing to a contiguous array of item array pointers.
 * 
 * @param noofsortarrays The number of arrays to sort included in the
 * array of items arrays.
 * 
 * @param metric The metric array of type T in the template is used to
 * sort the lists.
 * 
 * @param itemsize The size of each of the items to sort.
 * 
 * @param left The left most item to include in the sort.
 * 
 * @param right The right most item to include in the sort. */
template <class T> void Quicksorter<T>::recurseQuicksortNArray(void **items, int noofsortarrays, T *metric, size_t itemsize, int left, int right)
{
   // if the left element number is smaller than the right element
   // number (sanity check)
   if (left < right)
   {
      // randomise pivot as one somewhere between the left element and
      // right element
      int firstpivot = (rand() % ((right + 1) - left)) + left;
      // do partitioning into list a (below pivot) and list b (above
      // pivot)
      int pivotnewindex = recursePartitioningNArray(items, noofsortarrays, metric, itemsize, left, right, firstpivot);
      // quicksort list a
      recurseQuicksortNArray(items, noofsortarrays, metric, itemsize, left, pivotnewindex - 1);
      // quicksort list b
      recurseQuicksortNArray(items, noofsortarrays, metric, itemsize, pivotnewindex + 1, right);
   }
}

/** Move the quick sorting pivot to the appropriate place.
 * 
 * @param items The items to sort as a void pointer pointing to a
 * contiguous array of items.
 * 
 * @param metric The metric array of type T in the template is used to
 * sort the lists.
 * 
 * @param itemsize The size of each of the items to sort.
 * 
 * @param left The left most item to include in the sort.
 * 
 * @param right The right most item to include in the sort.
 * 
 * @param pivot The pivot position. */
template <class T> int Quicksorter<T>::recursePartitioning(void *items, T *metric, size_t itemsize, int left, int right, int pivot)
{
   // allocate a temporary swap area
   void *tmpswp = (void *)malloc(itemsize);
   T tmpswp_T;
   // the pivoting value is the fpmetric at the pivot point
   T pivotval = metric[pivot];
   // store index is left - 1, so first use will be left
   int storeindex = left - 1;
   // swap out the pivot item to the far right
   recurseSwap(items, itemsize, pivot, right, tmpswp);
   recurseSwap(metric, sizeof(T), pivot, right, (void *)&tmpswp_T);
   // move through all the indexes in this partition from left to
   // right
   for (int i = left; i < right; i++)
   {
      // if the item metric is less than the pivot item metric
      if (metric[i] < pivotval)
      {
         // increment the stored index
         storeindex++;
         // swap the item whose metric less than the pivots metric
         // value into the stored index
         recurseSwap(items, itemsize, storeindex, i, tmpswp);
         recurseSwap(metric, sizeof(T), storeindex, i, (void *)&tmpswp_T);
      }
   }
   // swap the pivot back from the far right into the next position
   // (which is of course guaranteed correct)
   recurseSwap(items, itemsize, storeindex + 1, right, tmpswp);
   recurseSwap(metric, sizeof(T), storeindex + 1, right, (void *)&tmpswp_T);
   // free the swapping space
   free(tmpswp);
   // return the new index for the pivot item
   return storeindex + 1;
}

/** Choose and move the quick sorting pivot to the appropriate place.
 * 
 * @param items An array of arrays of items to sort as a void pointer
 * pointer pointing to a contiguous array of item array pointers.
 * 
 * @param noofsortarrays The number of arrays to sort included in the
 * array of items arrays.
 * 
 * @param metric The metric array of type T in the template is used to
 * sort the lists.
 * 
 * @param itemsize The size of each of the items to sort.
 * 
 * @param left The left most item to include in the sort.
 * 
 * @param right The right most item to include in the sort.
 * 
 * @param pivot The pivot position. */
template <class T> int Quicksorter<T>::recursePartitioningNArray(void **items, int noofsortarrays, T *metric, size_t itemsize, int left, int right, int pivot)
{
   // allocate a temporary swap area
   void *tmpswp = (void *)malloc(itemsize);
   T tmpswp_T;
   // the pivoting value is the fpmetric at the pivot point
   T pivotval = metric[pivot];
   // store index is left - 1, so first use will be left
   int storeindex = left - 1;
   // swap out the pivot item to the far right
   for (int k = 0; k < noofsortarrays; k++) recurseSwap(items[k], itemsize, pivot, right, tmpswp);
   recurseSwap(metric, sizeof(T), pivot, right, (void *)&tmpswp_T);
   // move through all the indexes in this partition from left to
   // right
   for (int i = left; i < right; i++)
   {
      // if the item metric is less than the pivot item metric
      if (metric[i] < pivotval)
      {
         // increment the stored index
         storeindex++;
         // swap the item whose metric less than the pivots metric
         // value into the stored index
         for (int k = 0; k < noofsortarrays; k++) recurseSwap(items[k], itemsize, storeindex, i, tmpswp);
         recurseSwap(metric, sizeof(T), storeindex, i, (void *)&tmpswp_T);
      }
   }
   // swap the pivot back from the far right into the next position
   // (which is of course guaranteed correct)
   for (int k = 0; k < noofsortarrays; k++) recurseSwap(items[k], itemsize, storeindex + 1, right, tmpswp);
   recurseSwap(metric, sizeof(T), storeindex + 1, right, (void *)&tmpswp_T);
   // free the swapping space
   free(tmpswp);
   // return the new index for the pivot item
   return storeindex + 1;
}

/** Swap at the bottom of the recursion.
 * 
 * @param items The arrays of items to work on (can be the metric T)
 * 
 * @param itemsize The size of the items.
 * 
 * @param a The index a to swap with the index b.
 * 
 * @param b The index b to swap with the index a.
 * 
 * @param tmp A temporary storage area. */
template <class T> void Quicksorter<T>::recurseSwap(void *items, size_t itemsize, int a, int b, void *tmp)
{
   // Swaps items of specified length; if they are the same index,
   // don't bother
   if (a == b) return;
   // tmp = a
   memcpy(tmp, ((char *)items) + (a*itemsize), itemsize);
   // a = b
   memcpy(((char *)items) + (a*itemsize), ((char *)items) + (b*itemsize), itemsize);
   // b = tmp
   memcpy(((char *)items) + (b*itemsize), tmp, itemsize);
}

#endif
